The present invention relates to a system and method for generating random numbers. Random numbers play an important role in the use of pseudo random number generators, which are useful for cryptography and for various network security applications.
The quality of a pseudo random generator is based upon the unpredictability of its output. This unpredictability is in turn based partly upon the randomness of the numbers ("seeds") used to start the generator. The more random the seeds, the more unpredictable and better is the output of a well-designed pseudo random generator.
In practice, finding good random data for a seed can be problematic. It is difficult to generate numbers that are sufficiently random for most applications without resorting to hardware devices that rely upon natural phenomena with apparently random features. Such devices include physical noise generators, gas discharge tubes, and leaky capacitors. However, such devices are not generally suitable for use in a secure networking environment; it would be impractical (e.g., expensive) to require every node on a secure network that requires random numbers to have such a hardware device.
A known method of generating random numbers using the clock of a UNIX-based computer is called Truerand. Truerand obtains random numbers by counting a loop over a predetermined time supplied by a real time clock (ITIMER.sub.-- REAL in a UNIX system). When the predetermined time expires, the computer generates an signal (using SIGALRM in a UNIX system) and the loop stops counting. The least significant bits of the loop count (i.e., the number of times the loop was counted) provides random data that is further manipulated to provide random numbers that pass several chi-squared tests for randomness.
The loop count randomly varies in its least significant bits from execution to execution of Truerand due to randomness in the way Truerand is executed on a timesharing system. As Truerand executes, it is swapped out so that another queued process can execute. When this occurs, the loop stops counting, but the clock in Truerand (e.g., ITIMER.sub.-- REAL) continues to run while Truerand waits for its next slice of processor time. When Truerand is swapped in, the loop resumes counting. The loop stops counting after a predetermined elapsed time is reported from the computer clock (e.g., ITIMER.sub.-- REAL), triggering an signal (SIGALRM). In this way, the loop count varies (particularly in the least significant bits, which change the most rapidly) with a randomness that corresponds to the random way in which the processor swaps in and out processes in a timesharing environment.
The randomness of the loop count is enhanced by granularity in the computer clock. That is, the way in which the elapsed time is reported from the computer clock (ITIMER.sub.-- REAL) and triggers the signal varies from execution to execution of Truerand due to the changing state of the computer. This causes further unpredictable variations in the loop count, particularly in the least significant bits.
A disadvantage of Truerand is that it requires the use of the ITIMER.sub.-- REAL timer and the SIGALRM signal when implemented in UNIX, one of the most commonly used timesharing operating systems. ITIMER.sub.-- REAL or SIGALRM are reset each time either is used in a single UNIX application program. Hence, using ITIMER.sub.-- REAL and SIGALRM for Truerand can substantially limit the functionality of an application in which Truerand occurs because the programmer is precluded from using either the timer or the signal elsewhere in the same program. This problem can be addressed by letting the parent process to fork a child process to execute Truerand, but this increases the complexity of the application and can introduce unacceptable delays, especially when Truerand has to be called frequently to supply random numbers. Another way to address the problem with respect to ITIMER.sub.-- REAL is to save the timer value when calling Truerand and then reinstalling it when Truerand is finished executing. However, this introduces a substantial and unacceptable delay in execution while it is carried out.
Another disadvantage of Truerand is its slow speed. Truerand must run for a predetermined amount of time to obtain random data useful in constructing a random number. In a typical application with a 32-bit counter register (which contains the loop count), the least significant three bits from the register comprise the random data. Thus, to obtain enough random bits to form a 32-bit random number, the loop must be counted eleven times. In other words, the predetermined time for the loop must elapse eleven times to obtain sufficient random data to form a random 32-bit string, plus the time needed to swap in and out Truerand. Truerand generates only 25-30 bytes of random bits per second on a Sun Sparc-20 workstation. This is disadvantageously too slow for applications that require random numbers at rapid rates, such as generating a one-time pad, or frequently reseeding a pseudo random generator at a server.